#include <iostream>
using namespace std;

template < typename T >
void insertionSort(T list[], int arraySize)
{
  for (int i = 1; i < arraySize; i++)
  {
    /* insert list[i] into a sorted sublist list[0..i-1] so that list[0..i] is sorted. */
    double currentElement = list[i];
    int k;
    for (k = i - 1; k >= 0 && list[k] > currentElement; k--)
    {
      list[k + 1] = list[k];
    }

    // Insert the current element into list[k+1]
    list[k + 1] = currentElement;
  }
}

int main()
{

  double list[] =
  {
    1, 9, 4.5, 6.6, 5.7, -4.5
  };
  insertionSort(list, 6);

  for (int i = 0; i < 6; i++)
    cout << list[i] << " ";

  return 0;
}
